{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #破冰游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: iceBreakingGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #破冰游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>社团共有 <code>num</code> 为成员参与破冰游戏，编号为 <code>0 ~ num-1</code>。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 <code>target</code>，从 0 号成员起开始计数，排在第 <code>target</code> 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 7, target = 4\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 12, target = 5\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= target&nbsp;&lt;= 10^6</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof](https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof](https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n4', '12\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        x = 0\n",
    "        for i in range(2, num + 1):\n",
    "            x = (x + target) % i\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        dp = [0]*(num+1)\n",
    "                  # 只有一位成员i=1的时候，编号为0\n",
    "        for i in range(2, num+1):\n",
    "            dp[i] = (dp[i-1]+target)%i\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from sortedcontainers import SortedList\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        dic1=SortedList()\n",
    "        for i in range(1,num+1):\n",
    "            dic1.add(i)\n",
    "        remove_idx=0\n",
    "        while len(dic1)>1:\n",
    "            remove_idx=(remove_idx+target)  %len(dic1)\n",
    "            if remove_idx==0:remove_idx=len(dic1)\n",
    "            dic1.remove(dic1[remove_idx-1])\n",
    "            remove_idx-=1\n",
    "        return dic1[0]-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        n, m = num, target\n",
    "        dp = {}\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = (dp[i - 1] + m) % i\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from typing import *\n",
    "from graphlib import *\n",
    "import numpy as np\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        sl = SortedList(range(num))\n",
    "        p = target - 1\n",
    "        while len(sl) > 1:\n",
    "            p %= len(sl)\n",
    "            sl.pop(p)\n",
    "            p += target - 1\n",
    "            \n",
    "        return sl[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(num, target):\n",
    "    if num == 0:\n",
    "        return 0\n",
    "    x = f(num - 1, target)\n",
    "    return (target + x) % num\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        return f(num, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def iceBreakingGame(self, num: int, target: int) -> int:\n",
    "        if num == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return (self.iceBreakingGame(num - 1, target) + target) % num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
